심플렉스 법

심플렉스 법의 첫 번째 단계는 초기화이다. 이 단계에서는 주어진 선형 계획 문제를 표준형으로 변환하고, 초기 기저 가능해를 구성하는 것이 목표이다. 일반적인 선형 계획 문제는 최대화 또는 최소화 문제이며, 부등식 제약 조건을 포함한다. 초기화 과정에서는 모든 제약 조건이 등식이 되도록 잉여 변수나 부족 변수를 추가하여 표준형으로 만든다. 또한, 목적 함수와 우변의 상수항이 모두 음이 아닌 값이 되도록 정리한다.

초기 기저 가능해를 쉽게 얻기 위해, 표준형으로 변환된 문제에 인공 변수를 추가하는 방법이 자주 사용된다. 이는 큰 M 방법이나 2단계 심플렉스 법과 같은 기법의 기초가 된다. 초기화가 완료되면, 계수와 변수 값으로 구성된 초기 심플렉스 테이블이 만들어진다. 이 테이블은 이후 알고리즘 단계에서 피벗 연산을 반복하는 데 필요한 출발점을 제공한다. 초기화 단계의 정확성은 전체 심플렉스 법의 성공적인 수행을 보장하는 핵심 요소이다.

심플렉스 법의 핵심 반복 과정에서, 현재의 기저 가능해가 최적해인지를 판단하는 단계가 최적성 검사이다. 이 검사는 목적 함수의 계수를 바탕으로 이루어지며, 검사에 사용되는 지표를 감소 비용 또는 상대 비용 계수라고 부른다.

감소 비용은 비기저 변수가 한 단위 증가할 때 목적 함수 값의 변화량을 나타낸다. 모든 비기저 변수에 대한 감소 비용 값을 계산하여 검사를 수행한다. 최대화 문제의 경우, 모든 감소 비용이 0 이하이면 현재 해가 최적이다. 반대로, 감소 비용이 양수인 비기저 변수가 하나라도 존재하면, 그 변수를 진입 변수로 선택하여 해를 더 개선할 여지가 있다는 의미이다. 최소화 문제에서는 그 부호 조건이 반대로 적용된다.

이 검사 원리는 선형 계획법의 기본 정리, 즉 최적해가 존재한다면 반드시 기저 가능해 중 하나에서 찾을 수 있다는 점에 기반을 둔다. 따라서 심플렉스 법은 기저 가능해에서 다른 기저 가능해로 이동하며, 매번 최적성 검사를 통해 최적해 도달 여부를 확인하는 과정을 반복한다. 이 검사를 통과하지 못하면 알고리즘은 진입 변수 선택 단계로 넘어가 해를 개선하려 시도한다.

심플렉스 법의 핵심 반복 단계에서, 현재의 기저 가능해가 최적해가 아닐 경우, 목적 함수 값을 개선시킬 수 있는 비기저 변수를 기저로 진입시켜야 한다. 이때 선택되는 변수를 진입 변수라고 한다. 가장 일반적인 선택 기준은 최대 증가 법칙이다. 이는 목적 함수의 계수, 즉 감소 비용을 검토하여, 목적 함수를 가장 빠르게 개선시킬 수 있는 변수를 선택하는 방법이다. 구체적으로는, 최소화 문제에서 감소 비용이 가장 작은 음수인 변수를, 또는 최대화 문제에서 감소 비용이 가장 큰 양수인 변수를 진입 변수로 선택한다.

다른 선택 기준으로는 최대 개선 법칙이 있다. 이 방법은 변수가 진입했을 때 실제로 목적 함수 값이 얼마나 개선되는지를 계산하여, 그 개선량이 가장 큰 변수를 선택한다. 그러나 이 방법은 매번 가능한 개선량을 모두 계산해야 하므로 계산 부담이 커서 실제로는 자주 사용되지 않는다. 또한, 블랜드 법칙과 같은 방법은 진입 변수 선택 시 특정 규칙을 적용하여 알고리즘의 순환을 방지하는 데 주로 활용된다.

진입 변수의 선택은 알고리즘의 수렴 속도에 직접적인 영향을 미친다. 이상적으로는 최소 반복 횟수로 최적해에 도달할 수 있는 변수를 선택하는 것이 바람직하지만, 이를 미리 아는 것은 불가능하다. 따라서 실용적으로는 계산이 간단하면서도 효율적인 최대 증가 법칙이 널리 채택된다. 이 선택 단계는 이후의 이탈 변수 선택 및 피벗 연산과 긴밀하게 연결되어, 새로운 기저 가능해를 생성하는 과정의 시작점이 된다.

이탈 변수 선택 단계는 진입 변수로 선택된 변수가 기저에 들어오면서, 현재 기저에서 어떤 변수가 빠져나갈지를 결정하는 과정이다. 이는 새로운 해가 여전히 가능해 영역 내에 머물도록 보장하기 위한 핵심 단계이다.

진입 변수가 증가함에 따라 목적 함수 값은 개선되지만, 다른 제약 조건들로 인해 그 증가에는 한계가 있다. 각 제약 방정식에서 진입 변수의 계수를 분석하여, 진입 변수가 어느 정도까지 증가할 수 있는지를 계산한다. 이때 가장 엄격한 제약, 즉 진입 변수가 가장 작은 양의 증가폭만큼만 증가할 수 있게 하는 방정식이 이탈 변수를 결정한다. 이 계산은 최소 비율 테스트 또는 최소 비율 규칙으로 불린다.

구체적으로, 현재 기저 가능해와 진입 변수의 계수 벡터를 이용해 각 제약에 대한 비율을 구한다. 이때 분모는 진입 변수의 계수이며, 분자는 현재 기저 변수의 값이다. 분모가 양수인 제약들에 대해서만 비율을 계산하며, 이 중에서 가장 작은 비율 값을 가지는 제약의 현재 기저 변수가 이탈 변수로 선택된다. 만약 양의 계수를 가진 제약이 하나도 없다면, 진입 변수를 무한히 증가시킬 수 있다는 의미이므로 문제는 유계가 아니게 된다.

이탈 변수가 선택되면, 해당 변수는 기저에서 제거되어 값이 0이 되고, 진입 변수가 그 자리를 대신하게 된다. 이 과정을 통해 새로운 기저 가능해와 대응되는 심플렉스 표가 생성되며, 알고리즘은 다시 최적성 검사 단계로 돌아가 반복한다.

피벗 연산은 심플렉스 법의 핵심 단계로, 한 번의 반복마다 현재의 기저 가능해를 새로운 기저 가능해로 업데이트하는 과정이다. 이 연산은 선형 계획법의 심플렉스 테이블 또는 증강 행렬 형태에서 수행되며, 선택된 진입 변수와 이탈 변수를 교체하여 새로운 기저를 형성한다.

피벗 연산의 구체적 절차는 다음과 같다. 먼저, 진입 변수가 위치한 열을 피벗 열, 이탈 변수가 위치한 행을 피벗 행으로 정한다. 피벗 행과 피벗 열이 교차하는 원소를 피벗 원소라고 한다. 이후의 연산 목표는 피벗 원소를 1로 만들고, 피벗 열의 다른 모든 원소를 0으로 만들어 새로운 표준형을 얻는 것이다. 이는 기본적인 행 연산을 통해 이루어진다. 피벗 행의 모든 값을 피벗 원소로 나누어 피벗 원소를 1로 만든다. 그런 다음, 다른 각 행에서 피벗 행의 적절한 배수를 빼서 해당 행의 피벗 열 원소를 0으로 만든다. 이 연산은 목적 함수의 행을 포함한 테이블의 모든 행에 적용된다.

피벗 연산이 완료되면, 이탈 변수가 기저에서 제거되고 진입 변수가 새로운 기저 변수가 된다. 이로 인해 기저 해의 값이 업데이트되며, 목적 함수 값도 개선된다. 이 과정은 최적성 조건을 만족하거나 문제가 무계획임이 확인될 때까지 반복된다. 피벗 연산의 효율적 구현은 심플렉스 법의 성능에 직접적인 영향을 미치며, 수치적 안정성을 고려한 피벗 원소 선택 전략도 중요하게 연구된다.

심플렉스 법의 계산 과정에서 기저 가능해가 퇴화 상태일 때 발생하는 특수한 경우이다. 퇴화는 하나 이상의 기저 변수의 값이 0인 경우를 말하며, 이는 제약 조건의 기하학적 구조상 여러 개의 초평면이 한 점에서 만날 때 발생한다.

퇴화가 발생하면 심플렉스 법의 반복 과정에서 목적 함수 값의 개선 없이 기저만 순환하는 사이클링 현상이 일어날 수 있다. 이 경우 알고리즘이 무한 루프에 빠져 최적해에 도달하지 못할 위험이 있다. 사이클링을 방지하기 위해 블랜드 법칙이나 최소 지수 법칙과 같은 진입 변수 및 이탈 변수 선택 규칙이 개발되었다.

이러한 규칙들은 퇴화 상황에서도 변수의 선택 순서를 결정론적으로 정함으로써 사이클링을 방지한다. 실제 계산에서는 완전한 사이클링이 발생하는 경우는 드물지만, 퇴화는 선형 계획법 문제에서 흔히 관찰되는 현상이며, 알고리즘의 효율성에 영향을 미칠 수 있다.

심플렉스 법을 수행하는 과정에서 발생할 수 있는 특수한 경우 중 하나로, 문제의 목적 함수 값이 무한히 증가하거나 감소하여 유한한 최적해가 존재하지 않는 상황을 가리킨다. 이는 주로 문제의 제약 조건이 목적 함수의 개선 방향을 제한하지 못할 때 발생하며, 선형 계획법 문제가 유계되지 않았음을 의미한다.

알고리즘 진행 중 최적성 검사 단계에서 모든 비기저 변수의 감소 비용이 최적성을 만족함에도 불구하고, 어떤 비기저 변수를 증가시킬 때 제한하는 기저 변수가 존재하지 않는 경우에 이 현상이 확인된다. 즉, 이탈 변수 선택 단계에서 모든 계수가 0 또는 음수여서 최소 비율 검사를 수행할 수 없을 때, 해가 무한하다고 판단하고 알고리즘을 종료한다.

실제 응용 분야에서는 자원의 제약이 명확하지 않거나 모델링 오류로 인해 무한 해가 도출되는 경우가 있다. 예를 들어, 생산량을 무한히 늘릴 수 있다고 가정하는 비현실적인 수익 모델이나, 제약 조건을 누락한 경우에 해당한다. 따라서 심플렉스 법으로 무한 해 결론이 나오면, 원래 문제의 제약 조건과 목적 함수를 재검토해야 한다.

이러한 무한 해의 경우는 쌍대성 이론을 통해 다른 관점에서도 확인할 수 있다. 원 문제가 유계되지 않아 무한한 해를 가지면, 그 쌍대 문제는 실행 가능해를 갖지 않게 된다. 이는 심플렉스 법의 알고리즘적 결론과 수학적 이론이 일치함을 보여주는 한 예시이다.

심플렉스 법을 적용하기 위해서는 먼저 기저 가능해를 찾아야 한다. 표준형 선형 계획법 문제는 모든 변수가 음이 아니며 제약 조건이 등식으로 주어지는데, 이때 기저 변수에 해당하는 계수 행렬의 열벡터가 선형 독립이어야 한다. 문제의 제약 조건이 모두 '≤' 형태이고 우변이 음이 아닌 값일 경우, 느슨한 변수를 도입하면 쉽게 초기 기저 가능해를 얻을 수 있다. 느슨한 변수들은 초기 기저를 구성하는 변수가 된다.

그러나 '≥' 형태의 제약 조건이나 등식 제약이 포함된 경우, 또는 우변이 음수인 경우에는 이러한 간단한 방법이 적용되지 않는다. 이때는 인공 변수를 도입하는 방법을 사용한다. 각각의 '≥' 제약이나 등식 제약에 인공 변수를 추가하여, 이 인공 변수들로 구성된 초기 기저를 만든다. 그 후, 1단계 심플렉스 법 또는 큰 M 방법을 통해 인공 변수들을 기저에서 제거하고 진짜 문제의 초기 기저 가능해를 찾는다.

1단계 심플렉스 법은 인공 변수의 합을 최소화하는 보조 문제를 먼저 풀어, 그 최적값이 0이면 원래 문제의 가능해 영역이 비어있지 않음을 의미하며, 이때 얻은 해를 원래 문제의 초기 기저 가능해로 사용한다. 큰 M 방법은 목적 함수에 인공 변수에 매우 큰 벌칙 계수 M을 곱한 항을 추가하여, 알고리즘이 최적해를 찾는 과정에서 자연스럽게 인공 변수의 값을 0으로 만들도록 유도한다.

초기 기저 가능해를 찾는 이 과정은 심플렉스 법의 전체 수행 시간에 영향을 미칠 수 있으며, 효율적인 방법을 고안하는 것은 선형 계획법 해법의 중요한 연구 주제 중 하나이다.